'''
Created on 24/05/2011

@author: Jose Rodriguez Shaw, Sebastian Caredio, Agustin Ventura
'''

class TArbol(object):
    '''
    classdocs
    '''

    def __init__(self):
        self.raiz = None
    
    '''
    devuelve los datos de la raiz del arbol
    '''
    def obtenerRaiz (self):
        return self.raiz
    
    '''
    indica si el arbol es vacio, simplemente revisa si la raiz tiene o no un elemento
    '''
    def esVacio (self):
        
        return self.raiz == None  
    
    '''
    inserta un elemento en el arbol actual, del lado indicado
    el lado puede ser left o right
    '''
    def insertar (self, unElemento):
        if(self.esVacio()):
            self.raiz = unElemento
            #return True
        else:
            return self.raiz.insertar(unElemento, 'left')
    
    '''
    Devuelve una lista con el contenido del arbol en inorden
    orden n
    '''
    def inOrden(self):
        resultado = []
        if(not self.esVacio()):
            resultado.append(self.raiz.inOrden())
        return resultado

    '''
    devuelve el tamano del arbol
    '''
    def tamano (self):
        if ( self.esVacio() ):
            return 0
        else: 
            return self.raiz.tamano()

class TElemento(object):  
    '''
    classdocs
    '''
  
    def __init__(self, unosDatos):
        self.datos = unosDatos
        self.hijoDer = None
        self.hijoIzq = None
        self.visitado=False
    '''
    Visita el nodo para no volver a repetirlo mas adelante y el otro obtiene si esta visitado
    ''' 
    def visitar(self):
        self.visitado=True    
        
    def estaVisitado(self):
        return self.visitado    
    '''
    recibe de que lado del arbol queremos insertar
    lado puede ser o left o right
    '''
    def insertar(self, unElemento, lado):
        if lado == 'left':
            if (self.hijoIzq <> None):
                return self.hijoIzq.insertar(unElemento, lado)
            else:
                self.hijoIzq = unElemento
                return True
        elif lado == 'right':
                if (self.hijoDer <> None):
                    return self.hijoDer.insertar(unElemento, lado)
                else:
                    self.hijoDer = unElemento
                    return True
        else:
            return False
  
    '''
    Devuelve una lista con el contenido de los datos del nodo de este elemento y 
    de sus decendientes en inorden
    orden n
    '''
    def inOrden (self):
        resultado = []
        resultado.append('(')
        if(self.hijoIzq <> None):
            resultado.append(self.hijoIzq.inOrden())
        resultado.append(self.datos)
        if(self.hijoDer <> None):
            resultado.append(self.hijoDer.inOrden())
        resultado.append(')')
        return resultado
    
    '''
    Devuelve la cantidad de elementos que tiene el arbol 
    cuya raiz es este elemento
    orden n
    '''
    def tamano(self):
        tempTam = 1
        if ( self.hijoIzq <> None ):
            tempTam += self.hijoIzq.tamano()
        if ( self.hijoDer <> None ):
            tempTam += self.hijoDer.tamano()
        return tempTam
    
    '''
    Devulve la altura de un arbol
    orden n
    '''
    def altura(self):
        resultado = 0
        if ((self.hijoDer == None) and (self.hijoIzq == None)):
            return resultado
        if ((self.hijoDer == None) and (self.hijoIzq <> None)):
            resultado = self.hijoIzq.altura()
        else:
            if ((self.hijoIzq == None) and (self.hijoDer <> None)):
                resultado = self.hijoDer.altura()
            else:
                auxDer = self.hijoDer.altura()
                auxIzq = self.hijoIzq.altura()
                if (auxDer >= auxIzq):
                    resultado = auxDer
                else:
                    resultado = auxIzq
        resultado += 1
        return resultado